Today, many companies offer information and products via web sites. In many cases, a registration or subscription is required in order to access those sites. Suppose a set of users is granted access to a resource or service. This set changes over time: some users are added, and for some, the access to the resource or service is revoked. When a user is trying to access the resource, some verifier must make sure that this user is in this set. The immediate solution is to have the verifier look up a user in some database to make sure that a user is still allowed access to the resource in question. This solution is expensive in terms of communication. Another approach is of certificate revocation chains, where every day eligible users get a fresh certificate of eligibility. This is somewhat better since the communication burden is now shifted from the verifier to the user, but still suffers the drawback of high communication costs, as well as the computation costs needed to reissue certificates. Moreover, it disallows revocation at arbitrary time as need arises. A satisfactory solution to this task could not been provided, especially in a situation where the users in a system are anonymous at access time.
Accumulators were introduced by J. Benaloh and M. de Mare in their article “One-way accumulators: A decentralized alternative to digital signatures”, In Tor Helleseth, editor, Advances in Cryptology—EUROCRYPT '93, volume 765 of LNCS, pages 274-285, Springer-Verlag, 1994, as a way to combine a set of values into one short accumulator, such that there is a short witness that a given value was incorporated into the accumulator. Extending the ideas due to Benaloh and de Mare, N. Baric and B. Pfitzmann provided in their article “Collision-free accumulators and fail-stop signature schemes without trees”, In Walter Fumy, editor, Advances in Cryptology—EUROCRYPT '97, volume 1233 of LNCS, pages 480-494. Springer Verlag, 1997, a construction of the so-called collision-resistant accumulators, based on the strong RSA assumption. A handy property of accumulators as defined in the papers cited, is that the values can be added one-by-one at unit cost. However, the deletion of a value from an accumulator can not be made independent of the number of accumulated values.
From the above follows that there is a call for an efficient mechanism for granting and revoking privileges, e.g., access rights. The revocation of a membership or subscription should be easily possible with a minimum of computation and communication costs.